There has been explosive growth in Internet traffic due to the increased number of Internet users, various service demands from those users, the implementation of new services, such as voice-over-IP (VoIP) or streaming applications, and the development of mobile Internet. Conventional routers, which act as relaying nodes connected to sub-networks or other routers, have accomplished their roles well, in situations in which the time required to process packets, determine their destinations, and forward the packets to the destinations is usually smaller than the transmission time on network paths. More recently, however, the packet transmission capabilities of high-bandwidth network paths and the increases in Internet traffic have combined to outpace the processing capacities of conventional routers. Increasingly, routers are the cause of major bottlenecks in the Internet.
The limitations of conventional routers have been at least partially overcome by the introduction of massively parallel, distributed architecture routers. The use of optical connections has also greatly increased throughput. However, even massively parallel, distributed architecture routers have problems caused in part by the use of routing tables (or forwarding tables) that perform address translation lookups, among other things. Line speeds are increasing faster than processing speeds that perform routing table lookups. Since route lookups require the longest prefix match, this is a non-trivial problem. Internet Protocol Version 6 (IPv6) has aggravated this problem, because IPv6 uses 128-bit addresses, compared to the 32-bit addresses used in IPv4. Adding Type of Service (TOS) and Layer 4 addressing fields into the lookup value makes the problem still worse.
Routing tables with a million entries are not uncommon. Some lookup schemes (e.g., hashing, digital trees) are able to reduce the search time, but the large number of routing table entries leads to memory problems. It is prohibitively expensive and technically difficult to incorporate enough high-speed memory to support fairly flat search tables. As the number of memory chips increases, maintaining high performance becomes difficult due to layout considerations. As a result, memory access times are too slow to permit very deep search tables.
Some proposals use ternary content addressable memory (TCAM) devices to increase lookup speeds, but these devices are impractical due to expense and power consumption. Placing enough TCAMs on a circuit card to handle forwarding table lookups up to 144 bits wide, with up to a million entries, is prohibitive in both respects. Hashing and state-of-the-art search techniques are not adequate to keep routing tables within a reasonable size for cost and performance considerations and to keep the number of lookup stages low enough that memory access times enable lookups to keep up with line speeds. Thus, there is no practical method for doing IPv6 lookups at line speed for high-speed interfaces.
Therefore, there is a need in the art for an improved high-speed router. In particular, there is a need for an improved routing (forwarding) lookup mechanism that can perform lookups at line speed for a high-speed interface.